﻿// 0907train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <set>

using namespace std;

/*
 有一个考古学家发现一个石碑，但是很可惜 发现时其已经断成多段，
 原地发现 N 个断口整齐的石碑碎片，为了破解石碑内容
考古学家希望有程序能帮忙计算复原后的石碑文字，你能帮忙吗

备注
如果存在石碑碎片内容完全相同，则由于碎片间的顺序不影响复原后的碑文内容，
仅相同碎片间的位置变化不影响组合

输入描述
第一行输入 N，N 表示石碑碎片的个数
第二行依次输入石碑碎片上的文字内容 S 共有 N 组

输出描述
输出石碑文字的组合(按照升序排列)

输入
3
a b c
输出
abc
acb
bac
bca
cab
cba
 */
class Solution01
{
public:
    void backTrack(vector<string>&str_vec)
    {
        if (track.size()==str_vec.size())
        {
            string track_str;
            for (auto&str:track)
            {
                track_str += str;
            }
            result.push_back(track_str);
            return;
        }

        for (int i=0; i<str_vec.size(); i++)
        {
            if (checked[i]) continue;
            if (i > 0 && str_vec[i] == str_vec[i - 1] && !checked[i - 1])
                continue;

            track.push_back(str_vec[i]);
            checked[i] = true;
            backTrack(str_vec);
            checked[i] = false;
            track.pop_back();
            //for---
        }

	    //backTrack
    }
    Solution01(vector<string>&str_vec)
    {
        sort(str_vec.begin(), str_vec.end(),[](string&a, string&b)
        {
	        if (a.size()==b.size())
	        {
                return a < b;
	        }
            return a.size() < b.size();
        });
        checked.resize(str_vec.size());
        for (int i=0; i<str_vec.size(); i++)
        {
            //做选择
            track.push_back(str_vec[i]);
            checked[i] = true;
            //回溯
            backTrack(str_vec);
            //撤销选择
            track.pop_back();
            checked[i] = false;
        }

        set<string>result_set;
        for (auto&str:result)
        {
            result_set.insert(str);
        }

        vector<string>final;
        for (auto&str:result_set)
        {
            final.push_back(str);
        }

        //按照升序排列
        sort(final.begin(), final.end());
        for (auto&str: final)
        {
            cout << str << endl;
        }

        //Solution01
    }
private:
    vector<bool>checked;
    vector<string>track;
    vector<string>result;
};


/*
 给定一组不等式，判断是否成立并输出不等式的最大差(输出浮点数的整数部分)
要求：
1. 不等式系数为 double 类型，是一个二维数组；
2. 不等式的变量为 int 类型，是一维数组；
3. 不等式的目标值为 double 类型，是一维数组；
4. 不等式约束为字符串数组，只能是："=", ">"，">="，"<=", "<"
例如，不等式组：
a11x1+a12x2+a13x3+a14x4+a15x5<=b1
a21x1+a22x2+a23x3+a24x4+a25x5<=b2
a31x1+a32x2+a33x3+a34x4+a35x5<=b3
最大差 = max{(a11x1+a12x2+a13x3+a14x4+a15x5-b1),(a21x1+a22x2+a23x3+a24x4+a25x5-b2),(a31x1+a32x2+a33x3+a34x4+a35x5-b3)}
类型为整数(输出浮点数的整数部分)
输入描述
a11,a12,a13,a14,a15;a21,a22,a23,a24,a25;a31,a32,a33,a34,a35;x1,x2,x3,x4,x5;b1,b2,b3;<=,<=,<=

1. 不等式组系数(double类型)：
a11,a12,a13,a14,a15;
a21,a22,a23,a24,a25;
a31,a32,a33,a34,a35;
2. 不等式变量(int类型)：x1,x2,x3,x4,x5
3. 不等式目标值(double类型)：b1,b2,b3
4. 不等式约束(字符串类型)：<=,<=,<=

输出描述
true或者false，最大差

输入
2.3,3,5.6,7,6;11,3,8.6,25,1;0.3,9,5.3,66,7.8;1,3,2,7,5;340,670,80.6;<=,<=,<=
输出
false,458
 */
class Solution02
{
public:
    void initData(string& origin_str)
    {
        vector<string>str_vec_1;
        stringstream oh_sstream1(origin_str);
        string token;
        while (getline(oh_sstream1, token, ';'))
        {
            str_vec_1.push_back(token);
        }

        string character_str = str_vec_1.back();
        stringstream ch_sstream(character_str);
        while (getline(ch_sstream, token, ','))
        {
            character.push_back(token);
        }

        //a_vec的大小
        int a_size = character.size();
        vector<vector<string>>str_num_vec;
        for (int i = 0; i < a_size; i++)
        {
            vector<double>min_a_vec;
            string a_item = str_vec_1[i];
            stringstream a_sstream(a_item);
            while (getline(a_sstream, token, ','))
            {
                min_a_vec.push_back(stod(token));
            }
            a_vec.push_back(min_a_vec);
        }

        int x_index = a_size;
        string x_item = str_vec_1[x_index];
        stringstream x_sstream(x_item);
        while (getline(x_sstream, token, ','))
        {
            x_vec.push_back(stod(token));
        }

        int b_index = a_size + 1;
        string b_item = str_vec_1[b_index];
        stringstream b_sstream(b_item);
        while (getline(b_sstream, token, ','))
        {
            b_vec.push_back(stod(token));
        }
    }

    bool isVerify(double curr_sum, int index)
    {
        //"=", ">"，">="，"<=", "<"
        if (character[index] == "=")
        {
            return curr_sum == b_vec[index];
        }
        else if (character[index] == ">")
        {
            return curr_sum > b_vec[index];
        }
        else if (character[index] == ">=")
        {
            return curr_sum >= b_vec[index];
        }
        else if (character[index] == "<=")
        {
            return curr_sum <= b_vec[index];
        }
        
    	//"<"
    	return curr_sum < b_vec[index];
        //
    }

    Solution02(string&origin_str)
    {
        initData(origin_str);

        bool is_verify = true;

        int compute_i = 0;
        while (compute_i < b_vec.size())
        {
            double b_num = b_vec[compute_i];
            vector<double>a_num_v = a_vec[compute_i];

            double curr_sum = 0;
            for (int i=0; i<a_num_v.size(); i++)
            {
                curr_sum += a_num_v[i] * x_vec[i];
            }
            if (!isVerify(curr_sum, compute_i))
            {
                is_verify = false;
            }
            max_diff = max(max_diff, curr_sum - b_vec[compute_i]);
			compute_i++;
        }

        if (is_verify)
        {
            cout << "true";
        }
        else
        {
            cout << "false";
        }
        cout << ',' << int(max_diff);
	    //Solution02
    }
private:
    double max_diff = 0;
    vector<vector<double>>a_vec;
    vector<double>x_vec;
    vector<string>character;
    vector<double>b_vec;
};

/*
 一线运维人员在对通话流量进行监控，每一段时间内都是出现流量的高峰，流量有高有低形成一个个波峰波谷，运维人员想找到流量变化最快的波峰，你可以帮助他吗？

给定一个整数数组nums，代表采样点的流量值，请找到满足以下条件的三元组(i,j,k):
其中i<j<k，nums[i]<nums[j]且nums[j]>nums[k](即j是峰顶)，并找到所有满足条件的三元组中(k-i)的最小值

输入描述
第一行为n个整数，表示数组中的n个元素，0<=n<=100000

输出描述
返回所有满足条件的三元组中(k-i)的最小值。若不存在，返回-1。

示例1:
输入：
3 5 4 7 2 1
输出：
2
说明：
满足条件的三元组为[0,1,2],距离2

示例2：
输入：
4 3 2 1
输出：
-1
说明：
无法找到满足条件的三元组，返回-1
 */
class Solution03
{
public:
    unordered_map<int, vector<int>>num_map;
    Solution03(vector<int>&num_vec)
    {
        vector<int>left_stack_v;
        //nums[i]<nums[j]
        //左边比j小的
        for (int i=0; i<num_vec.size(); i++)
        {
            int curr = num_vec[i];
            while (!left_stack_v.empty() && num_vec[left_stack_v.back()] >= curr)
            {
                left_stack_v.pop_back();
            }
            if (!left_stack_v.empty())
            {
                num_map[i].push_back(left_stack_v.back());
            }
            left_stack_v.push_back(i);

        }
        vector<int>right_stack_v;
        for (int i=num_vec.size()-1; i>=0; i--)
        {
            int curr = num_vec[i];
            //nums[j]>nums[k]
            //i<j<k，右边比j小的
            while (!right_stack_v.empty() && num_vec[right_stack_v.back()]>=curr)
            {
                right_stack_v.pop_back();
            }
            if (!right_stack_v.empty())
            {
                //使用索引i，省得数字重复
                num_map[i].push_back(right_stack_v.back());
            }
            right_stack_v.push_back(i);
        }

        int result = INT_MAX;
        for (auto&map_item:num_map)
        {
	        if (map_item.second.size()==2)
	        {
                result = min(result, map_item.second[1]-map_item.second[0]);
	        }
        }

        if (result==INT_MAX)
        {
            cout << -1;
            return;
        }
        cout << result;
        //Solution03
    }
};

int main()
{
	{
        vector<int>num_vec;
        string input;
        getline(cin, input);
        string token;
        stringstream oh_sstream(input);
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
        //string input = "2.3,3,5.6,7,6;11,3,8.6,25,1;0.3,9,5.3,66,7.8;1,3,2,7,5;340,670,80.6;<=,<=,<=";
        string input;
        getline(cin, input);
        Solution02 solu(input);
        return 0;
	}
    int v_size;
    cin >> v_size;
    vector<string>str_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> str_vec[i];
    }

    Solution01 solu(str_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
